#include <stdio.h>
#include <vector>

using namespace std;

typedef vector<int> IV;
/**********
*方法一: 动态规划
*dp[i]: 以a[i]为最右元素的最长递增子序列的长度, i=0->n-1
*dp[i] = {
*   if(存在j,满足0<=j<i && a[j]<=a[i]) max(dp[j]) + 1 //严格模式下a[j] < a[i]
*   else 1
*}
*方法二: 动态渐进(dynamic gradual)
*L[i]: 当前长度为i+1的递增子序列的最小尾元素的在a中的索引
*性质: a[L[i]]: 具有单调性，包括严格模式
*方法三: 先计算a的递增排序a', 然后计算a和a'的最长公共子序列
***********/
class LISeq {
public:
    IV const &a;  
    int midx; //最长递增序列的最后元素索引 
    bool strict; //严格递增
private: 
    IV dp;
    IV prev; //prev[i]: 以a[i]为最右元素的最长递增序列的前驱元素在a中的索引
    IV L;
public:
    LISeq(IV const &a = {}, bool strict=false) : a(a), strict(strict) {}
    int lis_dp(void); //动态规划法
    int lis_dg(void);
    void lis_print(int id);
private:
    int find_pos(int val);
};



int LISeq::lis_dp(void) {
    int n = a.size();
    if(n<1) return 0;
    dp.resize(n);
    prev.resize(n);
    int i, j;
    midx=0; 
    for(i=0; i<n; i++) {
        dp[i] = 0;
        prev[i] = -1;
        for(j=0; j<i; j++) {
            if(dp[j]>dp[i] && (a[j]<a[i] || (a[j]==a[i] && !strict))){
                dp[i] = dp[j];
                prev[i] = j;
            }   
        }
        dp[i] += 1;
        if(dp[i] > dp[midx]) midx = i;
    }
    return dp[midx];
}

void LISeq::lis_print(int idx) {
    if(prev[idx] != -1) {
        lis_print(prev[idx]);
    }
    printf("%d ", a[idx]);
}


int LISeq::find_pos(int val) {
    int s = 0, e = L.size()-1;
    while(s <= e) {
        int mid = (s+e)/2;
        if(val > a[L[mid]]) {
            s = mid+1;
        }else if(val == a[L[mid]]){
            return strict ?mid: mid+1;
        } else {
            e = mid-1;    
        }
       
    }
    //s==e+1
    /**********
    if(s==0) { //val < a[L[0]]
        return s
    }else if(s<L.size()) { // a[L[e]]<val<a[L[s]]
        return s
    }else  { //s==L.size(), val>a[L[e]]
        return s
    }
    **********/
    return s;
}
int LISeq::lis_dg(void) {
    int n = a.size();
    if(n<1) return 0;
    
    L.resize(1);
    L[0] = 0; 
    prev.resize(n);
    prev[0] = -1;
    int pos; //当前遍历元素的在L中的插入位置
    int i, j;
    for(i=1; i<n; i++) {
        pos = find_pos(a[i]);
        if(pos >= L.size()) {
            prev[i] = *L.rbegin();
            L.push_back(i);
        }else {
            prev[i] = prev[L[pos]];
        }
        L[pos] = i; 
    }
    midx = *L.rbegin();
    return L.size();
}



int main(void) {
    IV a = { 6, 1, 5, 5, 8, 9, 0, 4, 7, 2, 3};
    LISeq lseq(a);
    int ml = 0;    

    printf("最长子序列：\n\t");
    ml = lseq.lis_dp();
    lseq.lis_print(lseq.midx);
    printf("\n\t长度: %d\n", ml);
    
    printf("最长子序列：\n\t");
    ml = lseq.lis_dg();
    lseq.lis_print(lseq.midx);
    printf("\n\t长度: %d\n", ml);
    
    lseq.strict = true;
    
    printf("最长子序列：\n\t");
    ml = lseq.lis_dg();
    lseq.lis_print(lseq.midx);
    printf("\n\t长度: %d\n", ml);

    printf("最长子序列：\n\t");
    ml = lseq.lis_dp();
    lseq.lis_print(lseq.midx);
    printf("\n\t长度: %d\n", ml);

    return 0;
}

